//一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [
//passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。 
//
// 给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 
//extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。 
//
// 一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。 
//
// 请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10⁻⁵ 以内的结果都会视为正确结果。 
//
// 
//
// 示例 1： 
//
// 
//输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
//输出：0.78333
//解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。
// 
//
// 示例 2： 
//
// 
//输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
//输出：0.53485
// 
//
// 
//
// 提示： 
//
// 
// 1 <= classes.length <= 10⁵ 
// classes[i].length == 2 
// 1 <= passi <= totali <= 10⁵ 
// 1 <= extraStudents <= 10⁵ 
// 
//
// Related Topics 贪心 数组 堆（优先队列） 👍 188 👎 0


package LeetCode.editor.cn;

import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2025-09-01 22:05:32
 * @description 1792.最大平均通过率
 */
public class MaximumAveragePassRatio{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MaximumAveragePassRatio fun=new MaximumAveragePassRatio();
	 	 Solution solution = fun.new Solution();
		solution.maxAverageRatio(new int[][]{{1,2},{3,5},{2,2}},2);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 提升最低的
    public double maxAverageRatio(int[][] classes, int extraStudents) {
		// 最大堆：按提升幅度 (p+1)/(t+1) - p/t 从大到小排序（即堆顶是提升最大的）
		PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> {
			double diff1 = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
			double diff2 = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
			// 比较：如果diff2 > diff1，则b的提升更大，应该排在前，但因为我们想要最大堆，所以这里返回负数表示b应该在前？
			// 实际上：我们希望提升幅度大的在堆顶，所以当比较a和b时，如果b的提升幅度更大，则b应该排在a前面（即返回负数）？
			// 标准写法：比较b和a的提升幅度，如果b的提升幅度大于a，则返回负数（表示b应该排在a前面），这样堆顶就是提升幅度最大的。
			return Double.compare(diff2, diff1);
		});

		for (int[] c : classes) {
			pq.offer(new double[]{c[0], c[1]});
		}

		for (int i = 0; i < extraStudents; i++) {
			double[] cur = pq.poll();
			double p = cur[0], t = cur[1];
			// 添加一个学生
			pq.offer(new double[]{p + 1, t + 1});
		}

		double totalRatio = 0;
		while (!pq.isEmpty()) {
			double[] cur = pq.poll();
			totalRatio += cur[0] / cur[1];
		}
		return totalRatio / classes.length;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
